import { Compare, defaultCompare, defaultEquals, ICompareFunction, IEqualsFunction } from '../util';
import LinkedList from './linked-list';
import { Node } from './models/linked-list-models';
/**
 * 保证元素按照一定规则顺序插入的链表结构。（这个顺序指的是元素的
 * 值的顺序，而链表本身因为指针是有顺序的，要区别开这两个“顺序”）
 * 需要重写push、unshift和insert这三个添加新元素的方法
 */
export default class SortedLinkedList<T> extends LinkedList<T> {
    protected compareFn: ICompareFunction<T>;
    constructor(
        equalsFn: IEqualsFunction<T> = defaultEquals,
        compareFn: ICompareFunction<T> = defaultCompare,
    ) {
        super(equalsFn);
        this.compareFn = compareFn;
    }
    /**
     * 重写push，按照顺序插入
     */
    public push(element: T) {
        this.insert(element);
    }
    /**
     * 重写unshift，按照顺序插入
     */
    public unshift(element: T) {
        this.insert(element);
    }
    /**
     * 有序链表的插入
     */
    public insert(element: T, index: number = 0): boolean {
        if (this.isEmpty()) {
            this.head = new Node<T>(element);
            this.count ++;
            return true;
        }
        // 新下标
        index = this.getIndexNextSortedElement(element);
        const node: Node<T> = new Node<T>(element);
        if (index === 0) { // 要放到第一个位置
            node.next = this.head; // 新元素与旧首部元素连接
            this.head = node;
        } else {
            const current: Node<T> = this.getElementAt(index - 1);
            node.next = current.next; // 将这个位置的元素放到node的next上
            current.next = node; // 再把node放到lastOne的next上，完成连接
        }
        this.count ++; // 数量更新
        return true;
    }
    /**
     * 按照compareFn的顺序规则来获取element需要插入的位置
     */
    private getIndexNextSortedElement(element: T) {
        let current = this.head;
        let i = 0;
        for (; i < this.count && current; i++) {
            const comp = this.compareFn(element, current.element);
            if (comp === Compare.LESS_THAN) { // 升序
                return i;
            }
            current = current.next;
        }
        return i;
    }
}
